package com.leetcode;

import java.util.LinkedList;
import java.util.List;


public class RotateList {

	public static void main(String[] args) {
		
		int[] arr={1,2,3,4,5};
		ListNode head=new ListNode(1);
		ListNode copyhead=head;
		for(int i=1;i<5;i++){
			head.next=new ListNode(arr[i]);
			head=head.next;
		}
		
		ListNode newHead=rotateRight(copyhead, 5);
		while(newHead!=null){
			System.out.print(newHead.val+" ");
			newHead=newHead.next;
		}
		
		ListNode lh=new ListNode(1);
		lh.next=new ListNode(2);
		ListNode newHead1=rotateRight(lh, 1);
		while(newHead1!=null){
			System.out.print(newHead1.val+" ");
			newHead1=newHead1.next;
		}
	}
	
    public static ListNode rotateRight(ListNode head, int k) {
        if(head==null||k==0) return head;
        int len=getLen(head);
       // if(k==len-1) return head;
        int begin=len-k%len;
        if(begin==len) return head;
        
        List<ListNode> listnode=new LinkedList<ListNode>();
        while(head!=null){
        	listnode.add(head);
        	head=head.next;
        }
       
        ListNode newHead=listnode.get(begin);
        ListNode newnewHead=newHead;
      
        ListNode lastHead=listnode.get(begin-1);
        lastHead.next=null;
        
        while(++begin<len){
        	newHead.next=listnode.get(begin);
        	newHead=newHead.next;
        }
        int i=0;
        while(i<len-k%len){
        	newHead.next=listnode.get(i);
        	newHead=newHead.next;
        	i++;
        }
        newHead.next=null;
        return newnewHead;
    }
    
    public static int getLen(ListNode head){
    	if(head==null) return 0;
        int count=0;
        while(head!=null){
        	++count;
        	head=head.next;
        	
        }
        return count;
    }
}
